public class Code2 {
    // 环形子数组最大和

    public int maxSubarraySumCircular(int[] nums) {
        // 1、创建 dp 表
        // 2、初始化
        // 3、填表
        // 4、返回值

        // 创建 dp 表
        // 观察题目，我们可以看到这里是一个环形数组，我们需要通过一些方式将这里的数组转化成非环形数组的形式
        // f[i] 中存储的是以 i 为结尾的 所有子数组 中的 最大和
        // g[i] 中存储的是以 i 为结尾的 所有子数组 中的 最小和
        // 最终将整个数组求和减去最小和 g[i] 就可以得到数组边缘处的最大值

        // 这里在创建的时候需要多添加一位虚拟节点
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];

        // 进行初始化操作
        // 将虚拟节点处初始化为 0
        f[0] = g[0] = 0;

        // 进行填表操作
        int sum = 0;
        int fmax = Integer.MIN_VALUE;
        int gmin = Integer.MAX_VALUE;
        // 填表时关注两部分：
        // 第一部分：就是 sums[i] 位置本身的数字
        // 第二部分：就是 sums[i] 位置的数与 i 位置结尾前所有的子数组中最大值与自身相加
        for(int i = 1; i <= n; i++){
            f[i] = Math.max(nums[i - 1], nums[i - 1] + f[i - 1]);
            fmax = Math.max(f[i], fmax);
            g[i] = Math.min(nums[i - 1], nums[i - 1] + g[i - 1]);
            gmin = Math.min(gmin, g[i]);
            sum += nums[i - 1];
        }
        // 返回时需要注意一点，即就是当 sums 数组中全部为 负数 的时候此时 sum 减去 g 表中的最小值此时为 0。这是不可取的。需要简单判断一下

        return sum == gmin ? fmax : Math.max(fmax, sum - gmin);
    }
}
